{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Necesary conditions for Knapsack problem\n",
    "### Install pyQUBO from Recruit Communications Co. Ltd.\n",
    "    pip install pyqubo\n",
    "### Install openJij from Jij Inc.  (startup from Tohoku University)\n",
    "    pip install openjij"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solve Knapsack problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### import pyQUBO, openJij, numpy and matplotlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyqubo  import Array,Constraint, Placeholder\n",
    "import openjij as jij\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Array, Constrains and Placeholders are convenient classes from pyQUBO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prepare binary variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 6\n",
    "Wmax = 3\n",
    "vartype = \"BINARY\"\n",
    "q = Array.create(\"q\",shape=N,vartype=vartype)\n",
    "y = Array.create(\"y\",shape=Wmax,vartype=vartype)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"q\" is name of variables  \n",
    "shape specifies the shape of variables as vector, matrix, or...  \n",
    "vartype selects -1 or 1 by \"SPIN\" and 0 or 1by \"BINARY\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Array([Binary(q[0]), Binary(q[1]), Binary(q[2]), Binary(q[3]), Binary(q[4]), Binary(q[5])])\n"
     ]
    }
   ],
   "source": [
    "print(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Array([Binary(y[0]), Binary(y[1]), Binary(y[2])])\n"
     ]
    }
   ],
   "source": [
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prepare values and weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = np.random.randint(1,N,N)\n",
    "w = np.random.randint(1,N,N)\n",
    "k = np.linspace(1,Wmax,Wmax)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define cost function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "E1 = Constraint((np.dot(w,q)-np.dot(k,y))**2,\"weight\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "E2 = Constraint((np.sum(y)-1)**2,\"y\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "E3 = - np.dot(c,q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "Lam1 = Placeholder('Lam1')\n",
    "Lam2 = Placeholder('Lam2')\n",
    "E_cost = Lam1*E1+Lam2*E2+E3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compile the cost function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = E_cost.compile()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Get qubo matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "feed_dict = {'Lam1': 5.0,'Lam2': 10.0}\n",
    "Q, offset = model.to_qubo(feed_dict=feed_dict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prepare simulation of quantum annealing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "#simulated quantum annealing\n",
    "sampler = jij.SQASampler(beta=10.0, gamma=1.0, trotter=4, num_sweeps=100)\n",
    "#simulated annealing\n",
    "#sampler = jij.SASampler(num_sweeps=1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is done by quantum Monte-Carlo simulation  \n",
    "gamma = strength of quantum fluctuation  \n",
    "trotter = Trotter number  \n",
    "num_sweeps = length of MCS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's simulate quantum annealing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "response = sampler.sample_qubo(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Show results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  q[0] q[1] q[2] q[3] q[4] q[5] y[0] y[1] y[2] energy num_oc.\n",
      "0    0    0    0    0    1    0    0    0    1    5.0       1\n",
      "['BINARY', 1 rows, 1 samples, 9 variables]\n"
     ]
    }
   ],
   "source": [
    "print(response)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### minimum sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 0, 0, 0, 1, 0, 0, 0, 1]], dtype=int8)"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "response.record[\"sample\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### decode solution through pyQUBO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "dsol, broken, energy = model.decode_solution(response.record[\"sample\"][0], feed_dict = feed_dict, vartype=vartype)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 0}\n"
     ]
    }
   ],
   "source": [
    "print(dsol[\"q\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: 0, 1: 0, 2: 1}\n"
     ]
    }
   ],
   "source": [
    "print(dsol[\"y\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
